package company.cvte;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

//        A->B,
//        B->C,
//        C->D,
//        E->F,
//        E->G,
//        F->H,
//        H->J,
//        J->K,
//        G->A

public class C1 {

    public static void main(String[] args) {
        List<Node> list = new ArrayList<>();
        list.add(new Node("A", "B"));
        list.add(new Node("B", "C"));
        list.add(new Node("C", "D"));
        list.add(new Node("E", "F"));
        list.add(new Node("E", "G"));
        list.add(new Node("F", "H"));
        list.add(new Node("H", "J"));
        list.add(new Node("J", "K"));
        list.add(new Node("G", "A"));
        
        System.out.println(judge(list));
    }

    public static boolean judge(List<Node> list) {
        // 起始位置
        HashSet<String> startNode = new HashSet<>();
        for (Node node : list) {
            startNode.add(node.getStart());
        }
        for (Node node : list) {
            startNode.remove(node.getEnd());
        }
        System.out.println(startNode);
        // 生成图
        HashMap<String, List<String>> dict = new HashMap<>();
        for (Node node : list) {
            List<String> orDefault = dict.getOrDefault(node.getStart(), new ArrayList<>());
            orDefault.add(node.getEnd());
            dict.put(node.getStart(), orDefault);
        }
        System.out.println(dict);
        // 校验是否有环
        for (String start : startNode) {
            boolean ans = helper(start, new HashSet<>(), dict);
            if (!ans)
                return false;
        }
        return true;
    }

    private static boolean helper(String node, HashSet<String> route, HashMap<String, List<String>> dict) {
        List<String> nextNodes = dict.get(node);
        for (String nextNode : nextNodes) {
            if (route.contains(nextNode))
                return false;
            HashSet<String> tmpRoute = new HashSet<>(route);
            tmpRoute.add(nextNode);
            helper(nextNode, tmpRoute, dict);
        }
        return true;
    }

}

class Node {

    String start;

    String end;

    public Node(String start, String end) {
        this.start = start;
        this.end = end;
    }

    public String getStart() {
        return start;
    }

    public void setStart(String start) {
        this.start = start;
    }

    public String getEnd() {
        return end;
    }

    public void setEnd(String end) {
        this.end = end;
    }
}
